题解 P4643@洛谷 【[国家集训队]阿狸和桃子的游戏】

题意简述

我们有一个 nnmm 边的无向图,有点权和边权。现在两个人将它按照自己的最优方案每次取一个点,分为两部分,求出此时他们的分差。


方法分析

边权不好处理,我们想到将它与点权合并。最容易想到的方法就是两个端点各加一半边权,这个方法也是正确的,正确性将在下方证明。

因为每个人都会按照自己的当前最优策略取,所以将整个权值排序后,编号为奇数的是一个人取的,偶数的是另一个人取的,我们只需要按照奇偶数分别算出总权值即可。

正确性证明

这里主要证明上面说的将边权与点权合并的正确性。

对于一条边 e(u,v,w)e(u,v,w),设两端点的初始权值为 au,ava_u,a_v,我们这里将两端点的权值改为了 au+w2,av+w2a_u+\frac{w}{2},a_v+\frac{w}{2}

情况一:u,vu,v 被同一个人取到。

此时,这个人的总权值为 au+av+2×w2=au+av+wa_u+a_v+2\times\frac{w}{2}=a_u+a_v+w,符合题意。

情况二:u,vu,v 被两人分别取到。

不妨设 uu 被第一个人取到。

此时,第一个人权值为 au+w2a_u+\frac{w}{2},第二个人权值为 av+w2a_v+\frac{w}{2}。最后要将答案相减,得到 auava_u-a_v,符合题意。

综上所述,这种方法正确。


代码与备注

在这份代码中,我们排序后按照从小到大顺序循环取值。由于题面保证 nn 为偶数,因此这个方法也没有问题。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;

int n, m; 
double a[N], s[2];

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++) scanf("%lf", &a[i]);
	for(int i=1;i<=m;i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		a[u] += w / 2.0;
		a[v] += w / 2.0; 
	}
	sort(a+1, a+1+n);
	for(int i=1;i<=n;i++) s[i&1] += a[i];
	printf("%.0lf\n", s[0]-s[1]);
	return 0;
}